package DFS;
import java.util.*;
/**
 * Created with Intellij IDEA.
 * Description;
 * User:TQ02
 * Data:2024-03-21
 * Time:19:53
 * Text：47. 全排列 II
 */
public class Text8 {
    List<List<Integer>> t1=new ArrayList<>();
    List<Integer> path=new ArrayList<>();
    boolean[] check;
    List<List<Integer>> t2=new ArrayList<>();
    List<Integer> path2=new ArrayList<>();
    boolean[] check2;
    void dfs(int[] nums){
        int num=path.size();
        if(nums.length==num){
            t1.add(new ArrayList<>(path));
            return;
        }
        List<Integer> numbers=new LinkedList<>();
        for(int i=0;i<nums.length;i++){
            if(numbers.contains(nums[i])){
                continue;
            }
            if(!check[i]){
                numbers.add(nums[i]);
                path.add(nums[i]);
                check[i]=true;
                dfs(nums);
                //恢复现场
                check[i]=false;
                path.remove(path.size()-1);
            }
        }
    }

    public List<List<Integer>> permute(int[] nums) {
        check=new boolean[nums.length];
        dfs(nums);
        return t1;
    }

    public void dfs2(int[] nums,int pos){
        if(nums.length == pos){
            t2.add(new ArrayList<>(path2));
            return;
        }

        for(int i=0;i<nums.length;i++){
            if(check2[i]==true || (i!=0 && nums[i]==nums[i-1] && check2[i-1] == false)){
                continue;
            }else {
                path2.add(nums[i]);
                check2[i]=true;
                dfs2(nums,pos+1);
                //恢复现场
                check2[i]=false;
                path2.remove(path2.size()-1);
            }
        }
    }

    public List<List<Integer>> permute2(int[] nums) {
        check2=new boolean[nums.length];
        Arrays.sort(nums);
        dfs2(nums,0);
        return t2;
    }
    public static void main(String[] args) {
        Text8 t1=new Text8();
        int[] array={1,1,2,1,8,7,7,7,3};
        t1.permute(array);
        t1.permute2(array);
        System.out.println();
    }
}
